#include <stdio.h>
#include "linkedlist_getNthNode.h"
#include "linkedlist_determineCycle.h"

#define NUMELEMENT 10

// Determine whether or not a cycle exists in the list
bool determineCycle(NODE* head) {
    NODE* fast, *slow;
    fast = slow = head;
    
    while(true) {
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        else if ((fast == slow && fast != head) || fast->next == slow) {
            return true;
        }
        else {
            slow = slow->next;
            fast = fast->next->next;
        }
    }
}

void test_linklist_determineCycle() {
	NODE* head = NULL;
	int data[NUMELEMENT] = {1, 3, 4, 1, 8, 6, 10, 3, 0, 1};
	
	for (int i = 0; i < NUMELEMENT; i++ ) {
		printf("Insert %d at the front of the list\n", data[i]);
		insertInFront(&head, data[i]);
	}

	printf("\nTraversing the list\n");
	traverseList(head);
	printf("\n");
	
	if (determineCycle(head))
		printf("Cycle existed!!\n");
	else
		printf("No cycle existed!!\n");
	printf("\n");
	
	// create a cycle in the list
	int Nth = 1;
	NODE* tmpNode1 = getNthNodeFromLast(head, Nth);
	printf("%dst Node to last = %d\n", Nth, tmpNode1->data);
	
	Nth = 5;
	NODE* tmpNode2 = getNthNodeFromLast(head, Nth);
	printf("%dth Node to last = %d\n", Nth, tmpNode2->data);
    
	printf("Connect two nodes\n");
	tmpNode1->next = tmpNode2;
	
	if (determineCycle(head))
		printf("Cycle existed!!\n");
	else
		printf("No cycle existed!!\n");
	printf("\n");
}
